/**
 *在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.
 *
 * 最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
 *
 * 给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
 *  https://leetcode.cn/problems/sliding-puzzle/description/
 */
class SlidingPuzzle {

    private static class Pair {//队列中的元素类型，String 表示当前情况，index表示0的位置
        String str;
        int index;
        public Pair(String str,int index) {
            this.str = str;
            this.index = index;
        }
    }

    /**
     * 法一：单向广度搜索
     * @param board
     * @return
     */
    public int slidingPuzzle(int[][] board) {
        char[] cs = new char[6];//将二维数组转为一维数组
        int[] dir = new int[]{-3,3,-1,1};//方向数组
        String tar = "123450";//最后的目标就是123450
        int zerPos =0;
        for(int i=0,k=0;i<2;i++) {
            for(int j=0;j<3;j++) {//将二维数组转为一维数组
                cs [k++] = (char)(board[i][j]+'0');
                if(board[i][j]==0) {
                    zerPos = i*3+j;//记录0的位置
                }
            }
        }
        //单向广搜
        int step = 1;
        Deque<Pair> qu = new LinkedList<>();
        Set<String> set = new HashSet<>();
        String start = new String(cs);
        if(start.equals(tar)) {
            return 0;
        }
        qu.addLast(new Pair(start,zerPos));
        while(!qu.isEmpty()) {
            int size = qu.size();
            while(size-->0) {
                Pair cur = qu.pollFirst();
                String curStr = cur.str;
                char[] curCs= curStr.toCharArray();
                zerPos = cur.index;
                for(int i=0;i<4;i++) {//将0进行上下左右交换
                    int nextIndex = zerPos+dir[i];
                    //如果越界或处于二维数组不能交换的位置则continue
                    if(nextIndex<0||nextIndex>5||(zerPos==2&&nextIndex==3)||(zerPos==3&&nextIndex==2)) {
                        continue;
                    }
                    swap(curCs,zerPos,nextIndex);//将0和替他位置进行交换
                    String nextStr = new String(curCs);
                    if(nextStr.equals(tar)) {//如果达成目标，直接返回即可
                        return step;
                    }
                    if(!set.contains(nextStr)) {//如果没有访问过
                        set.add(nextStr);
                        qu.addLast(new Pair(nextStr,nextIndex));//入队
                    }
                    swap(curCs,zerPos,nextIndex);//换回来
                }
            }
            step++;
        }
        return -1;
    }
    private void swap (char[] curCs,int a,int b) {
        char tmp = curCs[a];
        curCs[a] = curCs[b];
        curCs[b] = tmp;
    }

    /**
     * 法二：优化版：双向广度搜索
     */
    int[] dir = new int[]{-3,3,-1,1};//方向数组
    public int slidingPuzzleDouble(int[][] board) {
        char[] cs = new char[6];

        String tar = "123450";
        int zerPos =0;
        for(int i=0,k=0;i<2;i++) {
            for(int j=0;j<3;j++) {
                cs [k++] = (char)(board[i][j]+'0');
                if(board[i][j]==0) {
                    zerPos = i*3+j;
                }
            }
        }
        String start = new String(cs);
        if(start.equals(tar)) {
            return 0;
        }
        //双向广度搜索
        Deque<Pair> frontQu = new LinkedList<>();
        Map<String,Integer> frontMap = new HashMap<>();
        Deque<Pair> backQu = new LinkedList<>();
        Map<String,Integer> backMap = new HashMap();
        frontQu.addLast(new Pair(start,zerPos));
        frontMap.put(start,0);
        backQu.addLast(new Pair(tar,5));
        backMap.put(tar,0);
        while(!frontQu.isEmpty()&&!backQu.isEmpty()) {
            int ret = -1;
            if(frontQu.size()<=backQu.size()) {
                ret = update(frontQu,frontMap,backMap);
            } else {
                ret = update(backQu,backMap,frontMap);
            }
            if(ret!=-1) {
                return ret;
            }
        }
        return -1;

    }
    private int update(Deque<Pair> qu,Map<String,Integer> map,Map<String,Integer> anthor) {
        int size = qu.size();
        while(size-->0) {
            Pair cur = qu.pollFirst();
            String curStr = cur.str;
            int curIndex = cur.index;
            char[] curCs = curStr.toCharArray();
            for(int i=0;i<4;i++) {
                int nextIndex = curIndex+dir[i];
                if(nextIndex<0||nextIndex>5||(curIndex==2&&nextIndex==3)||(curIndex==3&&nextIndex==2)) {
                    continue;
                }
                swap(curCs,curIndex,nextIndex);
                String nextStr = new String(curCs);
                if(map.containsKey(nextStr)) {
                    swap(curCs,curIndex,nextIndex);
                    continue;
                }
                if(anthor.containsKey(nextStr)) {
                    return map.get(curStr)+anthor.get(nextStr)+1;
                } else {
                    qu.addLast(new Pair(nextStr,nextIndex));
                    map.put(nextStr,map.get(curStr)+1);
                }
                swap(curCs,curIndex,nextIndex);
            }
        }
        return -1;
    }
}